#!/usr/bin/python3
#! -*- coding:utf-8 -*-

import random
from caltime import runtime


# 找中间数的函数
def partition(ls, left, right):
    tmp = ls[left]  # 先把左侧第一个元素存到变量中
    while left < right:
        while left < right and ls[right] >= tmp:  # 从右侧找比tmp小的数
            right -= 1  # 往左侧走一步
            ls[left] = ls[right]  # 把右铡的值写到左铡空位上
        while left < right and ls[left] <= tmp:  # 从左侧找比tmp大的数
            left += 1  # 往右走一步
            ls[right] = ls[left]  # 把左侧的值写到右侧空位上
        ls[left] = tmp  # 把tmp归位

    return left


def _quick_sort(ls, left, right):
    if left < right:
        mid = partition(ls, left, right)
        _quick_sort(ls, left, mid)
        _quick_sort(ls, mid + 1, right)


@runtime
def quick_sort(ls):
    _quick_sort(ls, 0, len(ls) - 1)


lst = [random.randint(-100000, 100000) for _ in range(10000)]
# print('原列表>>>', lst)
quick_sort(lst)
# print('排序后的列表>>>', lst)'')'')

